package com.leetcode.根据算法进行分类.单调栈相关;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author: xiaomi
 * @date: 2021/2/8
 * @description: 739. 每日温度
 * https://leetcode-cn.com/problems/daily-temperatures/
 * {@link C_84_柱状图中最大的矩形}
 */
public class B_739_每日温度 {

    public static void main(String[] args) {

    }

    /**
     * 根据遍历的元素具有 LIFO 的特性，可以使用单调栈的思路。
     *
     * @param T
     * @return
     */
    public int[] dailyTemperatures(int[] T) {
        int len = T.length;
        if (len == 1) {
            return new int[]{0};
        }
        //使用 stack 记录 索引
        Deque<Integer> stack = new ArrayDeque<>();
        int[] res = new int[len];

        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peekLast()]) {
                int index = stack.removeLast();
                res[index] = i - index;
            }
            stack.addLast(i);
        }
        while (!stack.isEmpty()){
            int index = stack.removeLast();
            res[index]=0;
        }
        return res;
    }
}
